Linked lists are well known in the art, and various methods have been employed to manipulate linked lists. Linked lists are one of the most common data structures employed for the manipulation of data. Linked lists are particularly important within an operating system. Operating systems control a variety of resources simultaneously. A linked list might be used, for example, to hold requests for each individual resource.
Generally, linked lists can take two forms: (1) singly, circularly linked lists; or (2) doubly, circularly linked lists. Past methods of manipulating linked lists have concentrated on the handling of either singly or doubly linked lists, but not both. Thus, there is a need to flexibly manage a multiplicity of list types.
In the operation of a typical operating system, the system has a need to perform both Last In First Out (LIFO) operations and First In First Out (FIFO) operations. In the past, techniques to manipulate lists have concentrated on one of these operations, but not both. Operations of this type are very common for operating systems and multiprogramming subsystems, and as such, there is a need to be able to satisfy an operating system's need to frequently perform atomic LIFO and FIFO list manipulation instructions.
Past methods of maintaining doubly, circularly linked lists have centered around a single set of forward and backward pointers. Specific locations are set aside for these pointers by the operating system, and they are usually static. It is often difficult, if not impossible to have elements reside on multiple lists. Thus, there is a need to have location independence of forward and backward pointers.
Past methods have also had to concern themselves with elaborate error routines. If for example a plurality of instructions have been executed, in order to manipulate the list, and an error was detected, the system would need to run intricate routines to modify misplaced pointers. Thus, there is a need for advanced error detection so that gross programming errors can be detected immediately following the execution of the instruction.
An important property of linked list instruction is that they cannot be interrupted. When multiple processes have access to the same linked list, there is a need for synchronization between the processes. Past methods have locked an entire linked list so that other processes could not manipulate any part of the list simultaneously. Thus, there is a need for allowing part of the list to remain accessible while still providing a locking feature that allows list manipulation of multiple linked lists.